package com.likeycy.my.tree;

import java.util.Comparator;

/**
 * @ClassName: BalancedBinarySearchTree
 * @Description: 平衡二叉搜索树
 * @Author: sodagreen
 * @Date: 2021/3/22 22:49
 * @Version: 1.0
 */
public class BalancedBinarySearchTree<E> extends MyBinarySearchTree<E> {

    public BalancedBinarySearchTree() {
        this(null);
    }

    public BalancedBinarySearchTree(Comparator<E> comparator) {
        super(comparator);
    }

    /**
     * 失衡节点左旋转
     * @param grandparentNode
     */
    protected void rotateLeft(Node<E> grandparentNode) {
        Node<E> parent = grandparentNode.right;
        Node<E> child = parent.left;
        grandparentNode.right = child;
        parent.left = grandparentNode;

        afterRotate(grandparentNode, parent, child);
    }

    /**
     * 失衡节点右旋转
     * @param grandparentNode
     */
    protected void rotateRight(Node<E> grandparentNode) {
        Node<E> parent = grandparentNode.left;
        Node<E> child = parent.right;
        grandparentNode.left = child;
        parent.right = grandparentNode;

        afterRotate(grandparentNode, parent, child);
    }

    /**
     * 旋转后维护祖父节点、父节点、子节点的parent属性，并重新更新高度
     * @param grandparentNode
     * @param parent
     * @param child
     */
    protected void afterRotate(Node<E> grandparentNode, Node<E> parent, Node<E> child) {
        // 让parent成为子树的根节点
        parent.parent = grandparentNode.parent;
        if (grandparentNode.isLeftChild()) {
            grandparentNode.parent.left = parent;
        } else if (grandparentNode.isRightChild()) {
            grandparentNode.parent.right = parent;
        } else {
            // grandparentNode是root节点
            root = parent;
        }

        // 更新 child 的parent属性
        if (child != null) {
            child.parent = grandparentNode;
        }

        // 更新 grandparentNode 的 parent
        grandparentNode.parent = parent;


    }

    /**
     * 统一旋转二叉树节点，让二叉树平衡
     * @param r 子树的根节点，旋转后 root = d;
     * @param a
     * @param b ac的根节点
     * @param c
     * @param d 该节点旋转后称为左右子树的根节点，也就是root
     * @param e
     * @param f ed的根节点
     * @param g
     */
    protected void rotate(Node<E> r,
                        Node<E> a, Node<E> b, Node<E> c,
                        Node<E> d,
                        Node<E> e, Node<E> f, Node<E> g) {
        d.parent = r.parent;
        if (r.isLeftChild()) {
            r.parent.left = d;
        } else if (r.isRightChild()) {
            r.parent.right = d;
        } else {
            root = d;
        }

        // a-b-c
        b.left = a;
        if (a != null) {
            a.parent = b;
        }
        b.right = c;
        if (c != null) {
            c.parent = b;
        }


        // b-d-f
        f.left = e;
        if (e != null) {
            e.parent = f;
        }
        f.right = g;
        if (g != null) {
            g.parent = f;
        }


        // d-b-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;

    }
}
